#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution
{
public:
    int minFallingPathSum(vector<vector<int>> &matrix)
    {
        if (matrix.size() == 1)
            return matrix[0][0];
        vector<int> dp(matrix[0].size(), 0);
        vector<int> prev(matrix[0].size(), 0);
        for (int i = 0; i < matrix[0].size(); i++)
            prev[i] = matrix[0][i];
        for (int row = 1; row < matrix.size(); row++)
        {
            dp[0] = min(prev[0], prev[1]) + matrix[row][0];
            for (int col = 1; col < matrix[0].size() - 1; col++)
            {
                dp[col] = min(min(prev[col], prev[col + 1]), prev[col - 1]) + matrix[row][col];
            }
            dp[matrix[0].size() - 1] = min(prev[matrix[0].size() - 1], prev[matrix[0].size() - 2]) + matrix[row][matrix[0].size() - 1];
            prev = dp;
        }
        return *min_element(prev.begin(), prev.end());
    }
};

int main()
{
    cout << "Code931" << endl;
    Solution s;
    vector<vector<int>> matrix = {{2, 1, 3}, {6, 5, 4}, {7, 8, 9}};
    cout << s.minFallingPathSum(matrix) << endl;
    return 0;
}